package com.atguigui.leetcode;

/**
 * P面试题 17.19.消失的两个数字
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/9/26 8:48
 */
public class MissingTwoLcci {
    public static void main(String[] args) {
        Solution solution = new MissingTwoLcci().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 二分查找缺失数字
         *
         * @param nums
         * @return
         */
        public int[] missingTwo(int[] nums) {
            //保证n的长度
            int n = nums.length + 2;
            int sum = 0;
            for (int i : nums) {
                sum += i;
            }
            int ts = (1 + n) * n / 2 - sum; //两个缺失元素之和
            int m = ts / 2; //两个元素之间的“分界”（一个缺失元素大于这个值，另一个小于这个值）

            // 将问题转换为求一个缺失元素
            sum = 0;
            //在m之前必定缺失一个元素，先把这个数子找出来
            for (int i : nums) {
                if (i <= m) {
                    sum += i;
                }
            }
            int res = (1 + m) * m / 2 - sum;
            return new int[]{res, ts - res};
        }
    }
}
